package problems;

import java.util.HashSet;

import graph.Node;

public class RandomProblem implements Problem {

	
	//branching factor
	//total nodes
	//number of arcs to existing nodes
	
	double _minBranchingFactor;
	double _maxBranchingFactor;
	int _totalNodes;
	double _chanseForBackward;
	double _minBackwardArcs;
	double _maxBackwardArcs;

	int _goalValue;
	
	int _numArcs;
	int _numExspansions;
	
	public RandomProblem(int minBranchingFactor, int maxBranchingFactor, int totalNodes, double chanseForBackward, int minBackwardArcs, int maxBackwardArcs, int goalValue){
		_minBranchingFactor = minBranchingFactor;
		_maxBranchingFactor = maxBranchingFactor;
		_totalNodes = totalNodes;
		_chanseForBackward = chanseForBackward;
		_minBackwardArcs = minBackwardArcs;
		_maxBackwardArcs = maxBackwardArcs;
	}
	
	@Override
	public Node makeGraph() {
		//in the beggining we experimented with graphs with cycles, but we gave it up.
		int count = 0;
		_numArcs = 0;
		_numExspansions = 0;
		Node[] nodes = new Node[_totalNodes];
		int currentNode = 0;
		
		for (int i=0; i<_totalNodes; i++){
			nodes[i] = new Node(i);
		}
		
		count++;
		
		while(count < _totalNodes){
			_numExspansions++;
			int branchingFactor = Math.min(getRandomBranchingFactor(), _totalNodes - count);
			
			if (currentNode==count-1){
				branchingFactor = Math.max(branchingFactor, 1);
			}
			
			int numBackwardArcs = getRandomBackwardArcs(Math.min(currentNode,branchingFactor));
			if (currentNode==count-1){
				numBackwardArcs = Math.min(numBackwardArcs, Math.max(branchingFactor-1,0));
			}
			
			_numArcs+=branchingFactor;
			Node[] children = new Node[branchingFactor];
			
			
			
			HashSet<Integer> backwardNodes = getBackwardNodes(currentNode, numBackwardArcs, count, count+(branchingFactor-numBackwardArcs-1), currentNode-1);
			int pos = 0;
			
			for (Integer i: backwardNodes){		//make all backward arcs
				children[pos] = nodes[i.intValue()];
				pos++;
			}
			for (; pos<branchingFactor ; pos++){
				children[pos] = nodes[count];
				count++;
			}
			nodes[currentNode].setChildren(children);
			currentNode++;
		}
		
		_goalValue = Math.min((int)(Math.random()*(double)(_totalNodes - currentNode) + currentNode), _totalNodes-1);
		nodes[_goalValue].goal();
		for (;currentNode<_totalNodes; currentNode++){
			nodes[currentNode].setChildren(new Node[0]);
		}
		return nodes[0];
		
		
		
	}
	
	private HashSet<Integer> getBackwardNodes(int currentNode, int numBackwardArcs, int minChildren, int maxChildren, int maxNode) {
		HashSet<Integer> ans = new HashSet<Integer>();
		for(int i=0; i<numBackwardArcs; i++){
			double p = Math.random()*(double)(maxNode);
			int node = (int)(p+0.5);
			while (ans.contains(new Integer(node)) /*|| (node==currentNode) */|| (node >= minChildren && node<=maxChildren)){
//				System.out.println("Ans contains " + node);
				p = Math.random()*(double)(maxNode);
				node = (int)(p+0.5);
			}
//			System.out.println("Adding to ans " + ((int)(p+0.5)));
			ans.add(new Integer(node));
		}
		return ans;
		
	}

	private int getRandomBranchingFactor(){
		double p = Math.random();
		double ans = (_maxBranchingFactor - _minBranchingFactor)* p + _minBranchingFactor;
		return (int)(ans+0.5);
	}
	
	private int getRandomBackwardArcs(int limit){
		double p1 = Math.random();
		if (p1<_chanseForBackward){
			double p = Math.random();
			double ans = (_maxBackwardArcs - _minBackwardArcs)* p + _minBackwardArcs;
			return Math.min((int)(ans+0.5), limit);
		} else {
			return 0;
		}
	}
	
	@Override
	public int getNumArcs(){
		return _numArcs;
	}
	
	@Override
	public int getNumExspansions(){
		return _numExspansions;
	}
	
//	public static void main(String[] args) {
//		//attempt to generate a problem
//		Problem p = new RandomProblem(0, 5, 20, 0.6, 2, 4);
//		Node n = p.makeGraph();
//		System.out.println("number of arcs = " + p.getNumArcs());
//		System.out.println("number of exspansions = " + p.getNumExspansions());
////		String t = "";
////		synchronized (t) {
////			try {
////				t.wait();
////			} catch (InterruptedException e) {
////				// TODO Auto-generated catch block
////				e.printStackTrace();
////			}
////		}
//		
//	}
	
}
